package leetcode.code1039;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int len;
	int[] values;

	public int minScoreTriangulation(int[] values) {
		len = values.length;
		this.values = values;
		Integer[][] dp = new Integer[len][len];
		return f(0, len - 1, dp);
	}

	private int f(int l, int r, Integer[][] dp) {
		if (dp[l][r] != null) {
			return dp[l][r];
		}
		int size = (r + len - l) % len + 1;
		if (size == 2) {// 这一段只有2个点，不能分成三角形
			return 0;
		}
		if (size == 3) {// 这一段有三个点，就是这个三角形
			dp[l][r] = values[l] * values[(l + 1) % len] * values[r];
			return dp[l][r];
		}
		int cur = values[l] * values[r];
		int ans = Integer.MAX_VALUE;
		// 三个点以上情况，枚举[l,r]中间一个点i作为[l,r]上最后一个三角形
		for (int i = (l + 1) % len; i < r; i = (i + 1) % len) {
			int sum = cur * values[i] + f(l, i, dp) + f(i, r, dp);// 此时最小
			ans = Math.min(ans, sum);
		}
		dp[l][r] = ans;
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(144, this.minScoreTriangulation(H.str2array3("[3,7,4,5]")));
		H.compare(6, this.minScoreTriangulation(H.str2array3("[1,2,3]")));
		H.compare(13, this.minScoreTriangulation(H.str2array3("[1,3,1,4,1,5]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
